|
The "happy ending problem" (so named by Paul Erdős because it led to the marriage of George Szekeres and Esther Klein〔(A world of teaching and numbers - times two ), Michael Cowling, The Sydney Morning Herald, 2005-11-07, cited 2014-09-04〕) is the following statement: :Theorem: any set of five points in the plane in general position〔In this context, general position means that no two points coincide and no three points are collinear.〕 has a subset of four points that form the vertices of a convex quadrilateral. This was one of the original results that led to the development of Ramsey theory. The happy ending theorem can be proven by a simple case analysis: if four or more points are vertices of the convex hull, any four such points can be chosen. If on the other hand, the point set has the form of a triangle with two points inside it, the two inner points and one of the triangle sides can be chosen. See for an illustrated explanation of this proof, and for a more detailed survey of the problem. The Erdős–Szekeres conjecture states precisely a more general relationship between the number of points in a general-position point set and its largest convex polygon. It remains unproven, but less precise bounds are known. ==Larger polygons== proved the following generalisation: :Theorem: for any positive integer ''N'', any sufficiently large finite set of points in the plane in general position has a subset of ''N'' points that form the vertices of a convex polygon. The proof appeared in the same paper that proves the Erdős–Szekeres theorem on monotonic subsequences in sequences of numbers. Let ''f''(''N'') denote the minimum ''M'' for which any set of ''M'' points in general position must contain a convex ''N''-gon. It is known that * ''f''(3) = 3, trivially. * ''f''(4) = 5.〔This was the original problem, proved by Esther Klein.〕 * ''f''(5) = 9.〔According to , this was first proved by E. Makai; the first published proof appeared in .〕 A set of eight points with no convex pentagon is shown in the illustration, demonstrating that ''f''(5) > 8; the more difficult part of the proof is to show that every set of nine points in general position contains the vertices of a convex pentagon. * ''f''(6) = 17.〔This has been proved by . They carried out a computer search which eliminated all possible configurations of 17 points without convex hexagons while examining only a tiny fraction of all configurations.〕 * The value of ''f''(''N'') is unknown for all ''N'' > 6; by the result of it is known to be finite. On the basis of the known values of ''f''(''N'') for ''N'' = 3, 4 and 5, Erdős and Szekeres conjectured in their original paper that : They proved later, by constructing explicit examples, that : but the best known upper bound when ''N'' ≥ 7 is :〔. See binomial coefficient and big O notation for notation used here and Catalan numbers or Stirling's approximation for the asymptotic expansion.〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Happy ending problem」の詳細全文を読む スポンサード リンク
|